#include<stdio.h>
#include<windows.h>
#include<string.h>
#include<stdlib.h>
#include<conio.h>


typedef struct nod{
	char string[20];
	nod *sub[5];
}nod;

char *comparare(char *s1,char *s2){
	int i=0;
	int min=strlen(s1);
	if(min>strlen(s2))
		min=strlen(s2);
	char *aux=(char*)malloc(sizeof(char)*min);

	while(s1[i]==s2[i])
	{
		aux[i]=s1[i];
		i++;
	}
	aux[i]='\0';
	return aux;
}

char *rest(char *comparare,char *s2){

	int i=0,j=0;
	int m=strlen(comparare);
	int l=strlen(s2);
	if(m>l)
		return "";
	char *rest=(char*)malloc(sizeof(char)*(strlen(s2)-m+1));
	for(i=m;i<strlen(s2);i++)
	{
		rest[j]=s2[i];
		j++;
	}
	rest[j]='\0';
	return rest;
}

nod *nou(char *s){
	nod *el=(nod*)malloc(sizeof(nod));
	int i;
	strcpy(el->string,s);
	for(i=0;i<5;i++)
	{
		el->sub[i]=(nod*)malloc(sizeof(nod));
		strcpy(el->sub[i]->string,"\0");
	}
	strcpy(el->sub[1]->string,"*");
	return el;
}  

nod *split(nod *head,char *s){
	char comp[10];
	nod *el=(nod*)malloc(sizeof(nod));
	// rest + comp = head->string
	strcpy(comp,comparare(head->string,s));
	strcpy(head->string,rest(comp,head->string));
	el=nou(comp);
	el->sub[0]=head;
	el->sub[1]=nou(rest(comp,s));
	head=el;
	return head;
}

nod *root=NULL;


void adaugare(nod *&head,char *s){
	
	if(head==NULL || strcmp(head->string,"")==0)
	{
		head=nou(s);
		return;
	}
	char comp[20];
	int i,k;
	strcpy(comp,comparare(head->string,s));
	if(strcmp(head->string,comp)==0)
	{	
		if(strcmp(s,head->string)==0)
		{
			strcpy(head->sub[1]->string,"*");
			return;
		}
		k=0;
		for(i=0;i<5;i++)
		{
			if(strlen(comparare(head->sub[i]->string,rest(comp,s)))>0)
			{
				adaugare(head->sub[i],rest(comp,s));
				k=1;
				break;
			}
		}
		i=0;
		if(k==0)
		{
			while(strlen(head->sub[i]->string)!=0)
				i++;
			head->sub[i]=nou(rest(comp,s));
		}
	}
	else
		head=split(head,s);
}

nod  *cautare(nod *&head,char *s){
	nod *k=NULL;
	char comp[20];
	strcpy(comp,comparare(head->string,s));
	if(strcmp(head->sub[1]->string,"*")!=0 && strcmp(rest(comp,s),"*")==0 || strlen(s)-1<strlen(head->string)  )
		return k;
	if(strcmp(rest(comp,s),"*")==0 ) 
	{
		return head;
	}
	if(strlen(comp)>0)
	{
		int i;
		for(i=0;i<5;i++)
		{
			if(strlen(comparare(head->sub[i]->string,rest(comp,s)))>0 || strcmp(rest(comp,s),"*")==0  )
				k=cautare(head->sub[i],rest(comp,s));
		}
	}
	return k;
}






